package maxSizeSlices;

import java.util.Arrays;

public class Solution {
//    public int maxSizeSlices(int[] slices) {
//        // 给定一个长度为n的数组 从其中选择n个数且这n个数不相邻
//        // dp[i]表示 如果选择第i个披萨能拿的的最大值。
//        // dp[i] = max(dp[i-1],dp[i-2] + nums[i]) 拿i或者不拿i的最大值.
////        int m = slices.length;
////        boolean[] used = new boolean[m];
////        return dfs(slices,slices.length,used);
//    }
    //    private int dfs(int[] slices,int len,boolean[]used){
//        if(len == 3){
//            int max = Integer.MIN_VALUE;
//            for (int i = 0; i < slices.length; i++) {
//                if(!used[i]){
//                    max = Math.max(max,slices[i]);
//                }
//            }
//            return max;
//        }
//        int ans = 0;
//        int m = slices.length;
//        for (int i = 0; i < m; i++) {
//            if(!used[i]){
//                used[i] = true;
//                int alice = 0;
//                for (int j = 1; (j+i)%m !=i ; j++) {
//                    if(!used[(j+i)%m]){
//                        alice = (j+i)%m;
//                        break;
//                    }
//                }
//                used[alice] = true;
//                int bob = 0;
//                for (int j = 1; (m + i-j)%m !=i ; j++) {
//                    if(!used[(m + i-j)%m]){
//                        bob = (m + i-j)%m;
//                        break;
//                    }
//                }
//                used[bob] = true;
//                int sum;
//                sum = dfs(slices,len-3,used) + slices[i];
//                ans = Math.max(sum,ans);
//                used[i] = false;
//                used[bob] = false;
//                used[alice] = false;
//            }
//        }
//        return ans;
//    }

    // dp[i][j] 表表示在前i个披萨中选j个披萨的最大值。
    // 第i个披萨可以选也可以不选。dp[i][j] = max(dp[i-2][j-1]+slices[i],dp[i-1][j]);
    // 表示在剩下的len个披萨里面选择披萨的最大值.
    public int maxSizeSlices(int[] slices) {
        int[] v1 = new int[slices.length - 1];
        int[] v2 = new int[slices.length - 1];
        System.arraycopy(slices, 1, v1, 0, slices.length - 1);
        System.arraycopy(slices, 0, v2, 0, slices.length - 1);
        return Math.max(get(v1),get(v2));
    }
    private int get(int[] slices){
        int m = slices.length;
        int n = (m+1)/3;
        int[][] dp = new int[m][n+1];
        dp[0][1] = slices[0];
        dp[1][1] = Math.max(slices[0],slices[1]);
        for (int i = 2; i < m; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = Math.max(dp[i-2][j-1]+slices[i],dp[i-1][j]);
            }
        }
        return dp[m-1][n];
    }

//    public int maxSizeSlices(int[] slices) {
//        int m = slices.length;
//        int[][] meno1 = new int[m][m/3+1];
//        int[][] meno2 = new int[m][m/3+2];
//        int v1 = dfs(m-1,m/3,slices,1,meno1);
//        int v2 = dfs(m-2,m/3,slices,0,meno2);
//
//        return Math.max(v1,v2);
//    }
//    private int dfs(int i,int j,int[] slices,int start,int[][] meno){
//        if(j == 0){
//            return 0;
//        }
//        if(i<start+2&&j==1){
//            int ans = slices[start];
//            for (int k = start+1; k <=i; k++) {
//                ans = Math.max(slices[k],ans);
//            }
//            return ans;
//        }
//        if(i<start+2&&j!=1){
//            return 0;
//        }
//        if(meno[i][j]!=0){
//            return meno[i][j];
//        }
//        int ans = Math.max(slices[i]+dfs(i-2,j-1,slices,start,meno),dfs(i-1,j,slices,start,meno));
//        meno[i][j] = ans;
//        return ans;
//    }
}
